package 牛客101.链表;

public class 翻转指定的链表位置 {

    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode prev = new ListNode(-1);
        prev.next = head;
        ListNode begin = prev;

        for(int i = 0 ; i<m-1;i++)
        {
            begin = begin.next;
        }
// begin   leftNode    rightNode end
       ListNode rightNode = begin;
       for(int i =m;i<n-m;i++)
       {
         rightNode = rightNode.next;
       }
       //截取出一个子链串
        ListNode leftNode = begin.next;
        ListNode end = rightNode.next;

        // 4.斩断链表
        begin.next = null;
        rightNode.next = null;

        // 翻转链表

        reverse(leftNode);
        //重新拼接
        begin.next = rightNode;
        leftNode.next = end;


        return prev.next;



    }

    public ListNode reverse(ListNode head)
    {
        ListNode prev = null;
        ListNode cur = head;
        while(cur!=null)
        {
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        return  prev;
    }


    /*一次遍历*/
    public ListNode reverseBetween2(ListNode head,int m,int n){
        ListNode dum = new ListNode(-1);
        dum.next = head;
        ListNode prev = dum;

        for(int i = 0;i<m-1;i++)
        {
            prev = prev.next;
        }

        ListNode cur = prev.next;
        ListNode cur_Next = null;
        for(int i = 0;i<n-m;i++)
        {
            cur_Next  = cur.next;
            cur.next = cur_Next.next;
            cur_Next.next = prev.next;
            prev.next = cur_Next;
        }
        return dum.next;
    }
}
